package com.it.data_sort;

/**
 * @Author: CaoYouGen
 * @DateTime: 2023/05/22/8:57
 * @注释: 插入排序实现
 **/
public class InsertionSort {

    /**
     * @Author: CaoYouGen
     * @注释: 插入排序
     * @DateTime: 2023/5/22 8:59
     *
     * @param arr:
     * @return void
     */
    public static void insertSort(int[] arr){
        int len = arr.length;
        // 从第二个元素开始，将其插入到已排序的子数组中
        for (int i = 1; i < len; i++) {
            // 当前要插入的元素
            int key = arr[i];
            // 插入元素前一个元素的索引
            int j = i - 1;

            // 在已排序的子数组中寻找合适的插入位置（将比key大的元素后移一位）
            while (j >= 0 && arr[j] > key){
                arr[j + 1] = arr[j];
                j--;
            }
            // 在合适的位置插入key
            arr[j + 1] = key;
        }
    }

    public static void recursionInsertSort(int[] arr){
        toRecursionInsertSort(arr, 1);
    }


    /**
     * @Author: CaoYouGen
     * @注释: 插入排序(递归 执行逻辑)
     * @DateTime: 2023/5/23 12:47
     *
     * @return void
     */
    private static void toRecursionInsertSort(int[] arr, int low){
        if (low == arr.length){
            return;
        }

        int i = low - 1; // 0
        int key = arr[low];
        while (i >= 0 && arr[i] > key){
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = key;

        toRecursionInsertSort(arr, low + 1);
    }

}
